package leetcode_acm.backtrack;

import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月22日 20:22
 */
public class LetterCombinations {
    private List<String> list;
    //先打表,将映射的元素给填上
    private final char[][] str = new char[][]{
            "".toCharArray(), "".toCharArray(),
            "abc".toCharArray(), "def".toCharArray(),
            "ghi".toCharArray(), "jkl".toCharArray(),
            "mno".toCharArray(), "pqrs".toCharArray(),
            "tuv".toCharArray(), "wxyz".toCharArray()
    };
    public List<String> letterCombinations(String digits) {
        list = new LinkedList<>();
        char[] numbers = digits.toCharArray();
        int[] nums = new int[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            nums[i] = numbers[i] - '0';
        }
        backtrack(nums,0,new StringBuilder());
        return list;
    }
    private void backtrack(int[] nums,int index,StringBuilder sb){
        if(index == nums.length){
            list.add(sb.toString());
            return;
        }
        //然后开始单层的递归
        int stringIndex = nums[index];
        for(int i = 0;i < str[stringIndex].length;i++){
            //做出选择
            sb.append(str[stringIndex][i]);
            //递归回溯
            backtrack(nums,index+1,sb);
            sb.deleteCharAt(i);
        }
    }
}
